package org.example.leetcode;

/**
 * @version 1.0.0
 * @author: lynn
 * @description:
 * @date: 2021/8/12 9:48
 */
public class LC62 {

    //动态规划， leetcode 70，leetcode 198

    /**
     * 动态规划：从上往下走
     * 1.状态容器，一维或者二维数组，并完成初始化
     * 2.状态转移方程
     * 3.返回结果
     */
    public int uniquePaths(int m, int n) {
       int[][] dp=new int[m][n];
       //fixme 一般用到for循环，不用考虑空值
        for (int i = 0; i <m ; i++) {
            dp[i][0]=1;// fixme 初始化为 1
        }
        for (int i = 0; i <n ; i++) {
            dp[0][i]=1; // fixme 初始化为 1
        }

        for(int i=1;i<m;i++){
            for (int j = 1; j <n ; j++) {
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];//fixme 由于初始化是从0开始
    }


    public static void main(String[] args) {
        LC62 lc=new LC62();
        System.out.println(lc.uniquePaths(3,4));

    }
}
